1. Technical Field of the Invention
The present invention relates to a method and a program for cell labeling of volume data, for dividing space defined by boundary data that include one medium, or multiple-media, more than two, branching faces, holes, open shells, etc., and that are not always closed.
2. Description of the Related Art
In the research development or technology development field, CAD (Computer Aided Design), CAM (Computer Aided Manufacturing), CAE (Computer Aided Engineering) and CAT (Computer Aided Testing), for example, are employed as supporting means respectively for design, manufacturing, analyzing and testing.
Further, one set of volume data is co-owned to be used for sequentially performing different simulations, or for interacting simulation results with a manufacturing process, and this has gradually been spreading.
According to the conventional supporting means described above, the boundary face of a target or an objective article has an important meaning, and frequently, for example, the target is represented by using a boundary, and the inside of the boundary face is dealt with uniformly. In this case, inside/outside determining means is necessary for determining which is the inside or the outside of a two-dimensional or three-dimensional boundary plane or planes.
As conventionally known inside/outside determining means, there are (1) a ray crossing method (non-patent document 1), (2) a region growing (extending) method using boundary tracing (non-patent document 2), (3) a raster tracing in image processing (non-patent document 3), (4) a multi-directional tracing (non-patent document 2), (5) a method provided by Curless (non-patent 3), (6) a method provided by Szelistki or a method provided by Pulli, due to the use of an octree (non-patent document 5), and (7) non-patent documents 6 and 7 and patent documents 1 through 3. Furthermore, relevant patent documents 4 through 7 are publicly disclosed by the applicant the same as that of the present invention.
[Non-patent Document 1]
J. O'Rourke, “Computational Geometry in C (Second Edition”), p. 246, Cambridge University Press, 1998
[Non-patent Document 2]
Rosenfeld & Kak, translated by Nagao, “Digital image processing”, Modern Science Co., Ltd., pp. 332-357)
[Non-patent Document 3]
B. Curless and M. Levoy, “A Volumetric Method for Building Complex Models from range images.”, In Proceedings of SIGGRAPH '96, pages 303-312, August 1996)
[Non-patent Document 4]
R. Szeliski. “Rapid octree construction from image sequences.”
[Non-patent Document 5]
K. Pulli, T. Duchamp, H. Hoppe, J. McDonald, L. Hapiro, W. Stuetzle., “Robust meshes from multiple range maps.” Proceedings of International Conference on Recent Advances in 3-D Digital Imaging and Modeling, May 1997, pages 205-211.
[Non-patent Document 6]
Yonekawa, Kobori and Hisatsuwa, “Shape modeler using spatial division model”, Bulletin of Information Processing Society of Japan, Vol. 37, No. 1, pp. 60-69, 1996
[Non-patent Document 7]
Morimoto and Yamaguchi, “Recursive spatial division method and partial spatial classification, self crossings, and extension to overlapping curve”, Journal of Information Processing Society of Japan, Vol. 37, No. 12, December 1996
[Non-patent Document 8]
Weiler, K., The radial-edge structure: A topological representation for non-manifold geometric boundary representations, In Geometric Modeling for CAD Applications, North-Holland, (1988), pp. 3-36.
[Non-patent Document 9]
Cavalcanti, P. R., Carvalho, P. C. P., and Martha, L. F., Non-manifold modeling: an approach based on spatial subdivision, Computer-Aided Design, 29(3), (1997), pp. 209-220.
[Patent Document 1]
Japanese Laid-Open Patent Application Publication No. H8(1996)-96025, “Graphic Processing Method And Appratus for Same”
[Patent Document 2]
Japanese Laid-Open Patent Application Publication No. H8(1996)-153214, “Method for Generating Three-dimensional Orthogonal Grating Data”
[Patent Document 3]
Japanese Laid-Open Patent Application Publication No. 2003-44528, “Forming Method for Surface Grid of an Object”
[Patent Document 4]
Publication of the Japanese Patent No. 3,468,464, “Method for Storing Substance Data Obtained by Integrating Shape and Physical Property”
[Patent Document 5]
Japanese Laid-Open Patent Application Publication No. 2003-330976, “Inside/outside Determining Method for Boundary Data and Its Program”
[Patent Document 6]
International Publication No. 03/048980 pamphlet, “Method for Converting Tree-dimensional Shape Data into Cell Inner Data And Conversion Program”
[Patent Document 7]
International Publication No. 03/073335 pamphlet, “Method and Program for Converting Boundary Data into In-cell Shape”
The ray crossings method disclosed in non-patent document 1 is a method in which, when an input boundary face is present, whether the number of points where light (a ray) emitted by a specific point crosses the boundary is an even number or an odd number is determined, and when the number of points is an even number, it is determined that the visual point of the light ray is located outside an object, or when the number of points is an odd number, it is determined that the visual point is inside an object.
However, this means employed can not be applied when the light ray happens to contact a boundary, because a repeated root is provided, and thus, only one intersection point is obtained, while originally there are two intersection points. Therefore, there is also a problem in that this method can not be employed when boundary information is insufficient (when CAD data is to be read from different software, the missing of data sometimes occurs due to different ways of using expressions or due to an error in numerical values).
The region growing (extending) method, which employs boundary tracing in the image processing, to which only boundary information is given, is disclosed, for example, in non-patent documents 2, 8 and 9. However, there are problems such that the speed is slow because the performance of the process is extended toward the entire of the image, and identification can not be correctly performed when surface information is inadequate.
Raster tracing in the image processing is disclosed in non-patent document 2, and is a method whereby boundaries and a region sandwiched between the boundaries are traced while cells are scanned along a coordinate axis, such as the X-axis. Correct identification can not also be achieved with respect to an image obtained by quantizing inadequate boundary information (not a closed surface).
As a method for avoiding this, there is multi-directional tracing (the non-patent document 2), which is, however, low in the efficiency thereof.
The method offered by Curless for the reverse engineering field (method for reconstructing surface information based on a group of measurement points) is a robust method whereby external information, such as regularly arranged measurement points and directions of a plurality of cameras relative to a measurement object, is employed to define, for the entire field, an implicit function that is based on distance, and surface information is reconstructed. This method is disclosed in the non-patent document 3.
However, the method by Curless has drawbacks in the amount of data and the calculation time because distance field calculation is required for all of the cells. Further, a problem in accuracy is also pointed out, such that a distance function can not be correctly calculated for a thinner structure than the size of a cell and a face having an acute angle. This problem also results in an erroneous determination in the process of identification.
The method offered by Szeliski that uses an octree (the non-patent document 4) and the method offered by Pulli (the non-patent document 5) are also methods whereby relations between range data (distance data) for the obtained several targets and cells obtained by dividing a space using an octree are classified into three object divisions, i.e., inside, outside and boundaries, to thereby reconstruct the boundaries. According to these methods, since a projection operation is employed for each cell, a problem is encountered such that the processing is cumbersome and time-consuming and accordingly, calculations become unstable during the projecting operation.
A means disclosed in the non-patent document 6 can eventually express only two media by using three types of cells, i.e., outside, boundary and inside cells. Further, a problem must be encountered in which the expression is comprised of only a shape expression and no physical property value can be provided.
A means disclosed in the non-patent document 7 is directed to an inside/outside determining method used for input and branching, and is limited to two-dimensional sequential and finite use. Further, while a directed graph is employed, as one problem, this can not be employed for multi-media, three-dimensional use or discontinuous use.
Furthermore, the patent documents 1 through 3 disclose an art applicable to only two media, but to neither one medium nor three or more multi-media, and also are not applicable to any complicated surface data.
Additionally, although the patent documents 4 through 7 by the present Applicant are applicable to multi-media as a whole, the following problems, however, exist.
(1) It is difficult for a space to which multi-media belong to be partitioned along a boundary in a complicated shape.
(2) A limit exists in a target (boundary data) that can be dealt with as volume data proposed by the patent document 4.
In other words, when two manifolds, which are completely closed solids, are boundary data, dealing of multi-media is enabled. However, it is difficult to deal with boundary data such that a plurality of faces are branched from one side, or boundary data such that a hole is opened or is discontinued in the middle, i.e., it is difficult to deal with a non-manifold boundary, such as in the cases of face branching, a hole, an open shell, only one media, or three or more multi-media, etc.
It should be noted that, in the present invention, a manifold and a non-manifold are two-dimensional boundaries, and a solid, a volume, a medium and affiliated spaces are three-dimensional regions.
The present invention is contrived to solve the above-described problems. That is, an object of the present invention is to provide a method and a program for cell labeling of volume data, in which it is possible to deal with, as input targets, not only two outside and inside media, which are provided by boundary data for two manifolds that are completely closed solids, but also boundary data for a non-manifold that includes, for example, one medium that has an open shell boundary, three or more multi-media, face branching and a hole, and whereby a space partitioned by them can be divided in a quick and robust manner.
In other words, the object of the present invention is to provide a method and a program for cell labeling of volume data, in which different material (medium) information is added to each partitioned space segment, so as to be regarded as VCAD data (volume data), and various simulations are coupled/continued, and whereby volume data to which information has been added (also changed in a time series) can be employed for manufacturing and for an inspection, such as a comparison with a real object and an evaluation.